1. Field of the Invention
The present invention relates to a cryptographic key generation system for network communication, and in particular to a method and system that provide for multiple servers to collaborate and to furnish divided cryptographic keys to users, so that at arbitrary times the users, without having to notify the system, can acquire cryptographic keys by combining multiple public keys, whose private parts are only available after a certain period specified in the system.
2. Description of the Related Art
A key sharing system provides for the division of a cryptographic key among a plurality of servers; a well-known system for accomplishing this is a (t, k) threshold cryptography system by Shamir. According to this system, one secret is divided among k servers, and the secret can be obtained by the collaboration of t of the k servers. For this method, first, the following (txe2x88x921)th order polynomial for a specific field F is defined:
f(x)=f0+f1*x+f2*x2+ . . . +ftxe2x88x921*xtxe2x88x921xe2x80x83xe2x80x83(1)
The owner of secret first substitutes the secret for f0 in equation 1, and determines the remaining fk at random. Then, (i, f(i)) is transmitted as a share to the individual servers i. When t sets of shares are collected, the coefficients of the polynomial can be uniquely calculated and f0 can be acquired. According to the proactive secret sharing that was proposed by IBM""s T. J. Watson Research Center and described in Herzberg et al. U.S. Pat. No. 5,625,692, incorporated herein by reference, in the (t, k) threshold cryptography system, (i, f(i)) is not constantly maintained, but is dynamically changed by the performance of the updating process by the servers. The value f0 can be retained unchanged by so designing the updating process. Therefore, even when an assault is mounted on a server at a specific time and the share is stolen, security can be maintained as long as the shares are not stolen from t servers at the same time. In Canetti et al. U.S. Pat. No. 5,412,723, incorporated herein by reference, a dynamic public key is described that is in a state of constant preparation for use for communication between such a server group and a user.
In the commonly owned, copending application of applicant Kudo et al., Ser. No. 09/115,422, filed Jul. 14, 1998, now U.S. Pat. No. 6,381,695, issued Apr. 30, 2002, entitled xe2x80x9cEncryption System With Time-Dependent Decryptionxe2x80x9d and incorporated herein by reference, a time key certificate is defined, and a system by which a decryption server can determine a decryption time in accordance with the certificate is proposed. In the commonly owned, copending application of applicant Kudo, Ser. No. 09/272,873, filed Mar. 19, 1999, entitled xe2x80x9cMini Time Key Method and Systemxe2x80x9d and incorporated herein by reference, based on Boheh-Franklin Distributed RSA Key Generation Method, by Kudoh, Information Security Society, IEICE, 1998, it is stated that the security of the time key can be enhanced based on the fact that two servers can generate an RSA key pair without knowing the secret key.
However, the technique in Herzberg et al. has as its objective the constant sharing of an unchanged item of secret that is provided in advance. Even though the shares are dynamically changed by the proactive secret sharing method, the original secret is unchanged, and the cyclic feature and the time concept using that feature are not included in this technique. In Canetti et al., updating of a communication key is included, but the process does not include the concept of a time key. Furthermore, in the secret sharing process, first, an owner of secret is defined, so that the owner generates and divides a cryptographic key and distributes it to the servers. Therefore, by an effort that is directed towards this owner, the cryptographic key can be obtained in advance.
Furthermore, a single time key server is provided in Kudo et al., and the server is in charge of the management of the decryption time. In Kudo, even though a plurality of time key servers are provided, the time key servers independently determine whether the decryption time has been reached, so that the servers are separately in charge of the operational security for a cryptographic key.
It is, therefore, one object of the present invention to provide a method and a system for safely generating a cryptographic key that is separately provided to a plurality of servers.
It is another object of the present invention to provide a method and a system for separately generating a cryptographic key, depending on the time, for a plurality of servers.
It is an additional object of the present invention to provide a method and a system for periodically generating a cryptographic key.
It is a further object of the present invention to provide a method and a system whereof a server is not in charge of the operational security for a cryptographic key.
It is still another object of the present invention to provide a method and a system whereby a user is enabled, at an arbitrary time and without the system being notified to combine multiple public keys to obtain a cryptographic key.
It is a still additional object of the present invention to provide a method and a system whereby a time key having a higher security can be generated by multiple servers.
It is a still further object of the present invention to provide a method and a system whereby calculation of cryptographic keys for multiple servers is inhibited until a decryption time is reached.
To achieve the objects, according to the present invention, through the collaboration of multiple users a cryptographic key is generated for the servers. Specifically, random values are exchanged among the multiple servers, and based on these values, cryptographic keys are generated. Even though the cyclic feature of the cryptographic keys of the individual servers is lost by the exchange of the random values by at least two servers, the cyclic feature for the overall system can be maintained. Public keys for the multiple cryptographic keys are generated and are published. A new public key is generated by combining a plurality of public keys, and a corresponding cryptographic key is calculated by using the cryptographic keys of the individual servers. A key updating cycle (depending on the number of cryptographic key registers) is introduced for each server, so that decryption key information appears only during a specific cycle (this is called a cyclic system). A time key is generated by the cyclic system, and when a plurality of such cyclic systems are prepared and are autonomically activated, a safer time key can be generated. In the above described distributed system that includes multiple servers, key information can not be obtained even when one system maintains its own state. Since the servers periodically update their cryptographic keys, it is ensured that the calculation of a cryptographic key will be inhibited until a decryption time has been reached.